高考申論題
109年
[資訊處理] 資料結構
第 二 題
📖 題組：
四、若我們用相鄰矩陣（Adjacency Matrix）M來表示圖一中的無向圖G = (V, E)，請考慮下面的問題： 圖一、無向圖G = (V, E)
四、若我們用相鄰矩陣（Adjacency Matrix）M來表示圖一中的無向圖G = (V, E)，請考慮下面的問題： 圖一、無向圖G = (V, E)
請說明在用相鄰矩陣（Adjacency Matrix）表示的無向圖上，進行深度優先搜尋的時間複雜度，其中節點與邊的數量分別為|V| = n與|E| = m。（8分）
📝 此題為申論題
思路引導 VIP
本題重點在於結合「相鄰矩陣特性」與「DFS運作原理」推導時間複雜度。考生應先點出矩陣的大小（n×n），接著說明DFS走訪每個節點時，需耗費多少時間掃描該節點的鄰接點，最後歸納出總時間複雜度。
🤖
AI 詳解
AI 專屬家教
【解題思路】分析深度優先搜尋（DFS）在相鄰矩陣資料結構下的節點拜訪與鄰接邊檢查次數，進而推導出總時間消耗。 【詳解】 已知：無向圖 G = (V, E)，節點數 |V| = n，邊數 |E| = m。相鄰矩陣 M 是一個大小為 n × n 的二維陣列。
▼ 還有更多解析內容